/*
    2020年5月18日14:09:45
    设计一个算法，将一个头结点为A的单链表(其数据域为整数)分解成两个单链表A和B。
    使得A链表只含有原来链表中data域为奇数的结点，而B链表只含有原链表中data域为偶数
    的结点，且保持原来的相对顺序
*/
#include <iostream>
#include <malloc.h>
#ifndef NULL
#ifdef __cplusplus
#define NULL 0
#else /* __cplusplus */
#define NULL ((void *)0)
#endif /* __cplusplus */
#endif /* NULL */

typedef struct Node
{
    int data;
    struct Node *pNext;
} List, *pList;

void split(pList L)
{
	pList A = (pList)malloc(sizeof(List)), B = (pList)malloc(sizeof(List));
	pList p = A, q = B;
	while (L->pNext != NULL)
	{
		if (L->pNext->data % 2 == 0)
		{
			pList pNew = (pList)malloc(sizeof(List));
			pNew->data = L->pNext->data;
			p->pNext = pNew;
			pNew->pNext = NULL;
			p = p->pNext;
		}
		else
		{
			pList pNew = (pList)malloc(sizeof(List));
			pNew->data = L->pNext->data;
			q->pNext = pNew;
			pNew->pNext = NULL;
			q = q->pNext;
		}
		L = L->pNext;
	}

    //这是测试数据
	// cout << "list A = ";
	// Traverse_list(A);
	// cout << "list B = ";
	// Traverse_list(B);
}